"""
题目：https://leetcode-cn.com/problems/two-sum/
    给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
    你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
    你可以按任意顺序返回答案。
    示例 1：
    输入：nums = [2,7,11,15], target = 9
    输出：[0,1]
    解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

"""


"""
1、暴力解法
时间复杂度：O(n^2)
空间复杂度：O(1)
"""
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            num = nums[i]
            if target - num in nums[i+1:]:
                j = nums[i+1:].index(target - num)
                return [i,j + i + 1]
        return []

"""
2、利用哈希表，针对每一个x，查询哈希表中是否存在target - x，即可保证x不会和自己匹配。
时间复杂度：O(n)
空间复杂度：O(n)
"""
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = {}
        for i,num in enumerate(nums):
            if target - num in hashtable:
                return [hashtable[target - num], i]
            hashtable[num] = i
        return []